import java.util.PriorityQueue;

public class 数据流的中位数 {
    PriorityQueue<Integer> bigHeap;
    PriorityQueue<Integer> smallHeap;
    public MedianFinder() {
        // 大根堆存储小的一部分, 小根堆存储大的一部分
        // 误差不要超过 1
        smallHeap = new PriorityQueue<>();
        bigHeap = new PriorityQueue<>((a,b) -> {
            return b - a;
        });
    }

    public void addNum(int num) {
        int len1 = bigHeap.size();
        int len2 = smallHeap.size();
        // 如果长度相同
        if (len1 == len2) {
            // 两个都为空或者小于小的部分的最大值丢到大根堆
            if (bigHeap.isEmpty() || num <= bigHeap.peek()) {
                bigHeap.offer(num);
            } else {
                smallHeap.offer(num);
            }
        } else {
            // 小于小的部分的最大值丢到大根堆
            if (num <= bigHeap.peek()) {
                bigHeap.add(num);
            } else {
                smallHeap.add(num);
            }
            // 让大小差值维护到 1
            len1 = bigHeap.size();
            len2 = smallHeap.size();
            if (len1 > len2 + 1) {
                smallHeap.offer(bigHeap.poll());
            }
            if (len2 > len1 + 1) {
                bigHeap.offer(smallHeap.poll());
            }
        }
    }

    public double findMedian() {
        int len1 = bigHeap.size();
        int len2 = smallHeap.size();
        if (len1 == len2) {
            return (bigHeap.peek() + smallHeap.peek()) / 2.0;
        } else if (len1 > len2) {
            return bigHeap.peek();
        } else {
            return smallHeap.peek();
        }
    }
}
